from itertools import combinations


# 1 手动输入背包和物品参数
def get_positive_float(value, label):
    """
    确保输入的值是一个正数。
    如果无效，抛出详细的 ValueError。
    参数：
        value: 要检查的值。
        label: 当前值的描述，用于错误提示。
    返回：
        转换为浮点数的值。
    """
    try:
        value = float(value)
        if value <= 0:
            raise ValueError(f"{label} 必须是正数，但接收到: {value}")
        return value
    except ValueError as e:
        raise ValueError(f"无效输入：{label} 为 {value}。请提供正数！") from e


def input_knapsack_problem(n, weights, values, capacity):
    """
    接收直接传入的物品数量、重量、价值和背包容量，验证输入有效性。
    参数：
        n (int): 物品数量。
        weights (list): 每个物品的重量（正数列表）。
        values (list): 每个物品的价值（正数列表）。
        capacity (float): 背包容量（正数）。
    返回：
        dict: 包含物品数量、有效重量、价值列表和背包容量。
        如果验证失败，返回包含错误信息的字典。
    """
    try:
        # 验证物品数量
        n = int(get_positive_float(n, "物品数量"))
        if n != len(weights):
            return {"error": f"物品数量 ({n}) 与重量列表长度 ({len(weights)}) 不一致！"}
        if n != len(values):
            return {"error": f"物品数量 ({n}) 与价值列表长度 ({len(values)}) 不一致！"}

        # 验证重量列表
        validated_weights = []
        for i, weight in enumerate(weights):
            try:
                validated_weights.append(get_positive_float(weight, f"物品 {i + 1} 的重量"))
            except ValueError as e:
                return {"error": f"重量输入有误: {e}"}

        # 验证价值列表
        validated_values = []
        for i, value in enumerate(values):
            try:
                validated_values.append(get_positive_float(value, f"物品 {i + 1} 的价值"))
            except ValueError as e:
                return {"error": f"价值输入有误: {e}"}

        # 验证背包容量
        try:
            capacity = get_positive_float(capacity, "背包容量")
        except ValueError as e:
            return {"error": f"背包容量输入有误: {e}"}

        # 返回背包问题实例
        return n, validated_weights, validated_values, capacity

    except ValueError as e:
        return {"error": str(e)}


def fractional_knapsack(weights, values, capacity):
    """
    求解分数背包问题的贪心算法。
    参数：
        weights (list): 物品的重量列表。
        values (list): 物品的价值列表。
        capacity (float): 背包的总容量。
    返回：
        dict: 包括最优价值和选择的物品编号、重量、比例。
    """
    n = len(weights)
    # 计算单位重量价值，并排序
    items = [(values[i] / weights[i], weights[i], values[i], i + 1) for i in range(n)]  # 添加编号 i+1
    items.sort(reverse=True, key=lambda x: x[0])  # 按单位价值降序排列

    total_value = 0.0  # 背包中的总价值
    chosen_items = []  # 记录选择的物品比例

    for unit_value, weight, value, idx in items:
        if capacity <= 0:  # 背包已满
            break
        if weight <= capacity:
            # 完全放入物品
            total_value += value
            chosen_items.append((idx, weight, 1.0))  # 完全放入
            capacity -= weight
        else:
            # 部分放入物品
            fraction = capacity / weight
            total_value += value * fraction
            chosen_items.append((idx, weight, round(fraction, 2)))  # 部分放入
            capacity = 0  # 背包满了

    return {
        "total_value": total_value,
        "chosen_items": chosen_items
    }


def knapsack_dp(weights, values, capacity):
    """
    使用动态规划求解 0-1 背包问题的最优解。
    参数:
        weights (list): 每个物品的重量。
        values (list): 每个物品的价值。
        capacity (int): 背包的容量。
    返回:
        tuple: (总价值, 选择的物品列表 [(编号, 重量)])。
    """
    n = len(weights)
    # 初始化 DP 数组，dp[i][w] 表示前 i 个物品中，容量为 w 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # 填充 DP 表
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                # 可选择当前物品
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                # 无法选择当前物品
                dp[i][w] = dp[i - 1][w]

    # 回溯选择的物品
    total_value = dp[n][capacity]
    w = capacity
    selected_items = []

    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:  # 当前物品被选中
            selected_items.append((i, weights[i - 1]))
            w -= weights[i - 1]

    # 按物品编号升序排列
    selected_items.sort(key=lambda x: x[0])

    return total_value, selected_items


def knapsack_greedy_01(weights, values, capacity):
    """
    使用贪心算法求解 0-1 背包问题的近似解。
    参数:
        weights (list): 每个物品的重量。
        values (list): 每个物品的价值。
        capacity (float): 背包的容量。
    返回:
        tuple: (总价值, 选择的物品列表 [(编号, 重量)])。
    """
    n = len(weights)
    # 计算单位重量价值
    value_per_weight = [(values[i] / weights[i], i) for i in range(n)]
    # 按单位重量价值降序排序
    value_per_weight.sort(reverse=True, key=lambda x: x[0])

    total_value = 0
    selected_items = []

    for vpw, i in value_per_weight:
        if weights[i] <= capacity:
            # 完全装入该物品
            selected_items.append((i + 1, weights[i]))  # 保存物品编号和重量
            total_value += values[i]
            capacity -= weights[i]

    # 按物品编号升序排序
    selected_items.sort(key=lambda x: x[0])

    return total_value, selected_items


def knapsack_dp1(weights, values, capacity):
    """
    使用动态规划求解 0-1 背包问题的最优解，并记录动态规划表格。
    参数:
        weights (list): 每个物品的重量。
        values (list): 每个物品的价值。
        capacity (int): 背包的容量。
    返回:
        tuple: (总价值, 选择的物品列表 [(编号, 重量)]，动态规划表格)。
    """
    n = len(weights)
    # 初始化 DP 数组，dp[i][w] 表示前 i 个物品中，容量为 w 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # 填充 DP 表
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                # 可选择当前物品
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                # 无法选择当前物品
                dp[i][w] = dp[i - 1][w]

    # 回溯选择的物品
    total_value = dp[n][capacity]
    w = capacity
    selected_items = []

    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:  # 当前物品被选中
            selected_items.append((i, weights[i - 1]))
            w -= weights[i - 1]

    # 按物品编号升序排列
    selected_items.sort(key=lambda x: x[0])


    return total_value, selected_items, dp


def knapsack_dp(weights, values, capacity):
    """
    使用动态规划求解 0-1 背包问题的最优解，并记录动态规划表格。
    参数:
        weights (list): 每个物品的重量。
        values (list): 每个物品的价值。
        capacity (int): 背包的容量。
    返回:
        tuple: (总价值, 选择的物品列表 [(编号, 重量)]，动态规划表格)。
    """
    n = len(weights)
    # 初始化 DP 数组，dp[i][w] 表示前 i 个物品中，容量为 w 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # 填充 DP 表
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                # 可选择当前物品
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                # 无法选择当前物品
                dp[i][w] = dp[i - 1][w]

    # 回溯选择的物品
    total_value = dp[n][capacity]
    w = capacity
    selected_items = []

    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:  # 当前物品被选中
            selected_items.append((i, weights[i - 1]))
            w -= weights[i - 1]

    # 按物品编号升序排列
    selected_items.sort(key=lambda x: x[0])

    # 返回动态规划表格字符串
    table_str = "动态规划表格 (行：物品，列：容量):\n"
    table_str += "    " + "  ".join(f"{w:>3}" for w in range(capacity + 1)) + "\n"
    for i, row in enumerate(dp):
        table_str += f"{i:>3}: " + "  ".join(f"{v:>3}" for v in row) + "\n"

    return total_value, selected_items, table_str


def knapsack_bruteforce(weights, values, capacity):
    """
    使用蛮力法求解 0-1 背包问题的最优解，并记录每种情况的容量和。
    参数:
        weights (list): 物品的重量列表。
        values (list): 物品的价值列表。
        capacity (int): 背包的容量。
    返回:
        tuple: (最优总价值, 最优物品选择的索引列表, 所有情况的记录)
    """
    n = len(weights)
    best_value = 0  # 最优总价值
    best_combination = []  # 最优物品选择
    all_combinations = []  # 所有物品选择情况的记录

    # 枚举所有可能的物品选择组合
    for r in range(1, n + 1):  # 物品组合的大小从 1 到 n
        for comb in combinations(range(n), r):  # 获取所有大小为 r 的物品组合
            total_weight = sum(weights[i] for i in comb)  # 当前组合的总重量
            total_value = sum(values[i] for i in comb)  # 当前组合的总价值
            all_combinations.append((total_weight, total_value, comb))  # 记录每种组合情况

            if total_weight <= capacity and total_value > best_value:  # 不超过容量且总价值更大
                best_value = total_value
                best_combination = comb

    return best_value, best_combination, all_combinations


def knapsack_01(values, weights, W):
    n = len(values)
    dp = [[-1] * (W + 1) for _ in range(n + 1)]  # 初始化dp表格，全部为-1

    # 递归 + 记忆化
    def solve(i, w):
        if w < 0:
            return -float('inf')  # 返回负无穷表示不可行
        if i == 0 or w == 0:
            return 0  # 没有物品或者背包容量为0时，最大价值为0

        if dp[i][w] != -1:  # 如果已经计算过这个状态，直接返回
            return dp[i][w]

        # 递归选择当前物品或不选择
        dp[i][w] = max(solve(i - 1, w), values[i - 1] + solve(i - 1, w - weights[i - 1]))
        return dp[i][w]

    max_value = solve(n, W)

    # 反向推导选中的物品，确保按编号从小到大排序
    selected_items = []
    w = W
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:  # 如果选了第i个物品
            selected_items.append((i, weights[i - 1]))  # 记录物品编号和重量
            w -= weights[i - 1]

    # 按物品编号升序排序
    selected_items.sort(key=lambda x: x[0])  # 按编号排序

    return dp, max_value, selected_items
